
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
            total=8                              小端模式
    7                            0            inx 0x1122334455667788
    +------+-----------------+---+            0    +--+
    |      |    size         |   |                 |88|
    | A    |    B            | A |            1    +--+
    +------+-----------------+---+                 |77|
                            inx                    +--+
    7                                              |66|
    +-------------+---------------+                |55|
    |             |  size         |                |44|
    |             |  B            |                |33|
    +-------------+---------------+                |22|
    7                             0            7   |11|
    +-----------------------------+                +--+
    |1122.....................7788|
    +-----------------------------+
    mask0 保留val的区域B
    mask1 保留区域A
    其余区域补0
*/

static inline uint64_t mask1_val_uint64_big(uint64_t val, int inx, uint32_t size)
{
    register int h_inx = size + inx;
    register uint64_t tval = 0;
    if (h_inx < 8)
        tval = val >> (h_inx * 8) << (h_inx * 8);
    if (inx > 0)
        tval |= val << (8 - inx) * 8 >> (8 - inx) * 8;
    return tval;
}

static inline uint64_t mask0_val_uint64_big(uint64_t val, int inx, uint32_t size)
{
    int h_inx = 8 - size - inx;
    if (inx)
        val = val >> (8 * inx) << (8 * inx);
    if (h_inx > 0)
        val = val << h_inx * 8 >> h_inx * 8;
    return val;
}

typedef struct _CowMemNode CowMemNode;
typedef struct _CowMemNodeHeader CowMemNodeHeader;

struct _CowMemNode {
    union {
        // 将会出现大小端问题
        // 8字节数据,当写入当前数据不是地址对齐的则只写对应位,
        // 其他位保持base值,如果第一次写,初始化为0
        uint64_t val;
        uint8_t bytes[8];
    } data;

    // 当前快照的基础版本,即对应的level = 当前的level-1 或为0,
    // 当当前level=0时,base = NULL
    CowMemNode* base;

    // 快照版本, 0开始计数, 0表示最基础快照,
    // level-1是level的基础快照,当获取快照版本是大于当前最大level则表示使用最后的快照版本
    uint32_t level;
};

struct _CowMemNodeHeader {
    CowMemNode* latest; // 当前最新存储数据
    uint64_t addr; // 8字节对齐
};

static uint32_t cur_level = 0;

static CowMemNode* new_cow_mem_node()
{
    CowMemNode* n = (CowMemNode*)malloc(sizeof(CowMemNode));
    if (n == NULL) {
        perror("create node faild");
        abort();
    }
    memset(n, 0, sizeof(CowMemNode));
    return n;
}

static CowMemNodeHeader* new_node_header()
{
    CowMemNodeHeader* n = (CowMemNodeHeader*)malloc(sizeof(CowMemNodeHeader));
    if (n == NULL) {
        perror("create node faild");
        abort();
    }
    memset(n, 0, sizeof(CowMemNodeHeader));
    return n;
}

/**
 * 当非对齐写入时,且size大小超过当前节点时,报错, 即不支持 (addr&0x7) + inx > 8的写入访问
 * 非对齐访问由上层控制
 */
void write(CowMemNodeHeader* header, uint64_t addr, uint64_t val, uint32_t size)
{
    uint32_t inx = addr & 0x7llu;

    // 当写入超过当前节点地址时出错
    assert(inx + size <= 8 && header != NULL);
    assert(sizeof(uint64_t) == 8);

    CowMemNode* node = new_cow_mem_node();

    val = val << (8 * (8 - size)) >> (8 * (8 - size - inx));

    if (header->latest == NULL) {
        header->addr = addr >> 3 << 3; // 地址对齐
        // 光这个当inx+size小于8的时候没有补0
        // 补0高位和低位
        node->data.val = val;
    } else {
        node->data.val = val | mask1_val_uint64_big(header->latest->data.val, inx, size);
        node->base = header->latest;
        // level通过全局计数,以保证在回滚的时候能够简单处理
        // node->level = header->latest->level + 1;
        node->level = cur_level;
    }
    assert(header->addr == addr >> 3 << 3);
    header->latest = node;
    cur_level++;
}

/**
 * 读取数据,返回数据为
 * 
 *          total=8
 *  7                    addr    0(addr>>3<<3)
 *  +------+-----------------+---+
 *  |      |    size         |   |
 *  | A    |    B            | A |
 *  +------+-----------------+---+
 *                          inx
 *  返回数据格式                addr
 *  +------------+---------------+
 *  |            |  size         |
 *  |            |  B            |
 *  +------------+---------------+
 *  7                            0
 * 读取最新的版本数据,返回数据移动到低位
 */
uint64_t read(CowMemNodeHeader* header, uint64_t addr, uint32_t size)
{
    uint32_t inx = addr & 0x7u;
    // 当写入超过当前节点地址时出错
    assert(inx + size <= 8 && header != NULL && header->latest != NULL);
    assert(header->addr == addr >> 3 << 3);

    return header->latest->data.val << (8 * (8 - size - inx)) >> (8 * (8 - size));
}

/**
 * 读取数据,返回数据为
 * 
 *          total=8
 *  7                    addr    0(addr>>3<<3)
 *  +------+-----------------+---+
 *  |      |    size         |   |
 *  | A    |    B            | A |
 *  +------+-----------------+---+
 *                          inx
 *  返回数据格式                addr
 *  +------------+---------------+
 *  |            |  size         |
 *  |            |  B            |
 *  +------------+---------------+
 *  7                            0
 * 返回指定level的数据,如果当前最高level版本小于level则读取的是最新(最高)level的数据, 返回数据移动到低位
 */
uint64_t read_with_level(CowMemNodeHeader* header, uint64_t addr, uint32_t size, uint32_t level)
{
    uint32_t inx = addr & 0x7u;
    // 当写入超过当前节点地址时出错
    assert(inx + size <= 8 && header != NULL && header->latest != NULL);
    assert(header->addr == addr >> 3 << 3);
    CowMemNode* tnode = header->latest;
    while (tnode->level > level) {
        tnode = tnode->base;
    }
    return tnode->data.val << (8 * (8 - size - inx)) >> (8 * (8 - size));
}

/**
 * 删除从level开始的所有版本
 **/
void delete_from_level(CowMemNodeHeader* header, uint32_t level)
{
    if (header) {
        CowMemNode* tnode;
        while (header->latest && header->latest->level >= level) {
            tnode = header->latest;
            header->latest = tnode->base;
            free(tnode);
        }
    }
}

#include "list.c"

static int comare_addr(CowMemNodeHeader* a, CowMemNodeHeader* o)
{
    return a->addr - o->addr;
}

static void free_mem(CowMemNodeHeader* h)
{
}

static int match_addr(CowMemNodeHeader* h, uint64_t* addr)
{
    return (h->addr == *addr);
}

SimpleSortList list = {
    .first = NULL,
    .compare = comare_addr,
    .free = free_mem,
    .match = match_addr
};

uint64_t load_u64(uint64_t addr)
{
    uint64_t align_addr = addr >> 3 << 3;
    uint64_t rval = 0;
    int inx = addr & 0x7;
    CowMemNodeHeader* res = find_val(&list, &align_addr);
    if (res) {
        if (align_addr == addr)
            return res->latest->data.val;
        rval = read(res, addr, 8 - inx); // 出错
    }
    align_addr += 0x8;
    res = find_val(&list, &align_addr);
    if (res)
        rval |= read(res, align_addr, inx) << (8 * (8 - inx));
    return rval;
}

void store_u64(uint64_t addr, uint64_t val)
{
    uint64_t align_addr = addr >> 3 << 3;
    uint64_t rval = 0;
    uint32_t inx = addr & 0x7;
    CowMemNodeHeader* res = find_val(&list, &align_addr);
    if (res) {
        write(res, addr, val, 8 - inx);
    } else {
        res = new_node_header();
        write(res, addr, val, 8 - inx);
        insert(&list, res);
    }
    // 对齐地址访问
    if (!inx)
        return;

    align_addr += 0x8;
    res = find_val(&list, &align_addr);
    if (res) {
        write(res, align_addr, val >> 8 * (8 - inx), inx);
    } else {
        res = new_node_header();
        write(res, align_addr, val >> 8 * (8 - inx), inx);
        insert(&list, res);
    }
}

// int load_buf(uint64_t addr, uint32_t size, uint8_t* buf)
// {
// }

void test()
{
    uint64_t write_val_littler = 0x1122334455667788ULL;
    uint64_t tval;

    union {
        uint64_t val;
        uint8_t bytes[8];
    } ddd;
    ddd.val = write_val_littler;

    printf("org byte index: %llx, ", write_val_littler);
    for (int i = 0; i < 8; i++) {
        printf("%02x ", ddd.bytes[i]);
    }
    printf("\n");

    int size = 7;
    for (int i = 0; i < 8; i++) {
        tval = mask0_val_uint64_big(write_val_littler, i, size);
        printf("mak0: i=%d, size=%d, %016llx --> %016llx\n", i, size, write_val_littler, tval);
    }
    printf("=====\n");
    for (int i = 0; i < 8; i++) {
        tval = mask1_val_uint64_big(write_val_littler, i, size);
        printf("mak0: i=%d, size=%d, %016llx --> %016llx\n", i, size, write_val_littler, tval);
    }
    printf("right shift: %llx\n", write_val_littler >> 64);

    printf("========\n");
    CowMemNodeHeader node_header = { NULL };
    uint64_t write_val = 0x1122334455667788ULL;
    uint64_t read_val;
    for (int i = 0; i < 8; i++) {
        uint32_t size = 8 - i;
        size = 1;
        uint64_t addr = 0x10 + i;
        write(&node_header, addr, write_val, size);
        printf("write res: %d:%d %llx --> %016llx\n", i, size, write_val, node_header.latest->data.val);
    }
    write(&node_header, 0x10, write_val, 8);
    for (int i = 0; i < 7; i++) {
        uint32_t size = 8 - i;
        size = 2;
        uint64_t addr = 0x10 + i;
        read_val = read(&node_header, addr, size);
        printf("read addr: %lx: val: %lx, size: %d\n", addr, read_val, size);
    }
    printf("=====\n");

    delete_from_level(&node_header, 9);

    size = 1;
    uint64_t addr = 0x10;
    for (int i = 0; i < 20; i++) {
        addr = 0x12;
        read_val = read_with_level(&node_header, addr, size, i);
        printf("read-level val: %x %d --> %x\n", addr, i, read_val);
    }
}

void test_load_store()
{
    uint64_t val = 0x1122334455667788llu;
    uint64_t rval;
    uint64_t addr;
    for (int i = 0; i < 20; i++) {
        store_u64(i, val);
        rval = load_u64(i);
        printf("rval %llx --> %016llx\n", i, rval);
    }

    for (int i = 0; i < 20; i++) {
        addr = rand();
        store_u64(addr, addr);
        rval = load_u64(addr);
        printf("rval %llx --> %016llx\n", addr, rval);
    }
}

int main(int argc, char const* argv[])
{
    test();
    test_load_store();
    return 0;
}
